package leetcode;

import java.util.Arrays;
import java.util.Stack;

public class MaxSumOfRectangleNoLargerThanK {

	public static void main(String[] args) {
//		int[][] matrix = {{5,-4,-3,4},{-3,-4,4,5},{5,1,5,-4}};
//		int[][] matrix = {{2, 2, -1}};
		int[] array = {2, 2, -12, 4, -2, -3};
		
		
		int[][] matrix = {{27,5,-20,-9,1,26,1,12,7,-4,8,7,-1,5,8},{16,28,8,3,16,28,-10,-7,-5,-13,7,9,20,-9,26},
				{24,-14,20,23,25,-16,-15,8,8,-6,-14,-6,12,-19,-13},{28,13,-17,20,-3,-18,12,5,1,25,25,-14,22,17,12},
				{7,29,-12,5,-5,26,-5,10,-5,24,-9,-19,20,0,18},{-7,-11,-8,12,19,18,-15,17,7,-1,-11,-10,-1,25,17},
				{-3,-20,-20,-7,14,-12,22,1,-9,11,14,-16,-5,-12,14},{-20,-4,-17,3,3,-18,22,-13,-1,16,-11,29,17,-2,22},
				{23,-15,24,26,28,-13,10,18,-6,29,27,-19,-19,-8,0},{5,9,23,11,-4,-20,18,29,-6,-4,-11,21,-6,24,12},
				{13,16,0,-20,22,21,26,-3,15,14,26,17,19,20,-5},{15,1,22,-6,1,-9,0,21,12,27,5,8,8,18,-1},
				{15,29,13,6,-11,7,-6,27,22,18,22,-3,-9,20,14},
				{26,-6,12,-10,0,26,10,1,11,-10,-16,-18,29,8,-8},{-19,14,15,18,-10,24,-9,-7,-19,-14,23,23,17,-5,6}};
		MaxSumOfRectangleNoLargerThanK object = new MaxSumOfRectangleNoLargerThanK();
//		System.out.println(object.maxSum(array, 0));
		System.out.println(object.maxSumSubmatrix(matrix, -100));
	}
	
	//Runtime: 352 ms， beat 5%
	//bad idea
	public int maxSumSubmatrix(int[][] matrix, int k) {
		if(matrix == null || matrix.length <= 0){
            return 0;
        }
		int[][] historial = new int[matrix.length][matrix[0].length];
		historial[0] = matrix[0];
		int maxSum = Integer.MIN_VALUE;
		int cur = 0;
        for (int i = 1; i < matrix.length; i++) {
			for (int j = 0; j < matrix[0].length; j++) {
				historial[i][j] = historial[i - 1][j] + matrix[i][j];
			}
		}
        
        for (int i = 0; i < historial.length; i++) {
			for (int j = 0; j < historial[0].length; j++) {
				System.out.print(historial[i][j] + " ");
			}
			System.out.println();
		}
        int[] temp = new int[matrix[0].length];
        for (int i = 0; i < historial.length; i++) {
			for (int j = i; j < historial.length; j++) {
				if(i == 0){
					//他妈的，bug就是这样不知不觉产生的
					//之前是这样写的，这样最后会将temp = historial[length - 1]
					//在后面修改temp时，出现了将historial[length - 1]也修改了
					//temp = historial[j];
					//debug花了好长时间
					
					for (int m = 0; m < matrix[0].length; m++) {
						temp[m] = historial[j][m];
					}
				}else{
					for (int m = 0; m < matrix[0].length; m++) {
						temp[m] = historial[j][m] - historial[i - 1][m];
					}
				}
				for (int m = 0; m < matrix[0].length; m++) {
					System.out.print(temp[m] + "  ");
				}
				System.out.println("-----");
				cur = maxSum(temp, k);
				System.out.println(" i " + i + " --j " + j +  "  cur:" + cur);
				maxSum = Math.max(maxSum, cur);
			}
		}
        return maxSum;
    }

	private int maxSumOfHistoral(int[] historial, int k) {
		Stack<Integer> stack = new Stack<>();
		int area = 0;
		int maxArea = 0;
		for(int i = 0; i < historial.length; i++){
			while(!stack.isEmpty() && (historial[stack.peek()] >= historial[i])){
				int high = historial[stack.pop()];
				int length = stack.isEmpty() ? i : i - 1 - stack.peek();
				area = (i - 1 - length) * high;
				if(area <= k){
					maxArea = Math.max(area, maxArea);
				}
			}
			stack.push(i);
		}
		while(!stack.isEmpty()){
			int high = historial[stack.pop()];
			int length = stack.isEmpty() ? historial.length : historial.length - 1 - stack.peek();
			area = (historial.length - 1 - length) * high;
			if(area <= k){
				maxArea = Math.max(area, maxArea);
			}
		}
		return maxArea;
	}
	
	//wrong
	private int maxSumNoExceedK(int[] historial, int k) {
	    Arrays.sort(historial);
		int sum = Integer.MIN_VALUE;
		int curSum = historial[0];
		int left = 0;
		int right = 0;
		while(right < historial.length && left <= right){
		    if(curSum <= k){
		        right++;
		    	System.out.println("curSum: " + curSum);
		        sum = Math.max(curSum, sum);
		        if(right < historial.length){
		        	System.out.println("curValue: " + historial[right]);
		        	curSum += historial[right];
		        }else{
		        	break;
		        }
		    }else{
		        curSum -= historial[left++];  
		    }
		}
		return sum;
	}
	
	private int maxSum(int[] arr, int k){
		int res = Integer.MIN_VALUE;
		for (int i = 0; i < arr.length; i++) {
			int curSum = 0;
			for (int j = i; j < arr.length; j++) {
				curSum += arr[j];
				if(curSum <= k){
					res = Math.max(curSum, res);
				}
			}
		}
		return res;
	}
}
